//给你一个整数 n 。现有一个包含 n 个顶点的 无向 图，顶点按从 0 到 n - 1 编号。给你一个二维整数数组 edges 其中 edges[i] = 
//[ai, bi] 表示顶点 ai 和 bi 之间存在一条 无向 边。 
//
// 返回图中 完全连通分量 的数量。 
//
// 如果在子图中任意两个顶点之间都存在路径，并且子图中没有任何一个顶点与子图外部的顶点共享边，则称其为 连通分量 。 
//
// 如果连通分量中每对节点之间都存在一条边，则称其为 完全连通分量 。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：n = 6, edges = [[0,1],[0,2],[1,2],[3,4]]
//输出：3
//解释：如上图所示，可以看到此图所有分量都是完全连通分量。
// 
//
// 示例 2： 
//
// 
//
// 
//输入：n = 6, edges = [[0,1],[0,2],[1,2],[3,4],[3,5]]
//输出：1
//解释：包含节点 0、1 和 2 的分量是完全连通分量，因为每对节点之间都存在一条边。
//包含节点 3 、4 和 5 的分量不是完全连通分量，因为节点 4 和 5 之间不存在边。
//因此，在图中完全连接分量的数量是 1 。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 50 
// 0 <= edges.length <= n * (n - 1) / 2 
// edges[i].length == 2 
// 0 <= ai, bi <= n - 1 
// ai != bi 
// 不存在重复的边 
// 
//
// Related Topics 深度优先搜索 广度优先搜索 并查集 图 👍 36 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

//java:统计完全连通分量的数量
public class Q2685CountTheNumberOfCompleteComponents {
    public static void main(String[] args){
        Solution solution = new Q2685CountTheNumberOfCompleteComponents().new Solution();
        solution.countCompleteComponents(6, new int[][]{{0,1},{0,2},{1,2},{3,4}});
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    // 做邻接矩阵
    List<Integer>[] adjArr;
    // 标记是否访问过
    boolean[] visited;
    int vCount, eCount;
    public int countCompleteComponents(int n, int[][] edges) {
        adjArr = new ArrayList[n];
        visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            adjArr[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            adjArr[edge[0]].add(edge[1]);
            adjArr[edge[1]].add(edge[0]);
        }
        int res = 0;
        // 类似于题目547. 省份数量
        // 不同的是这里是完全连通分量
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                // 计算连通分量中点的个数
                vCount = 0;
                // 计算连通分量中边的个数
                eCount = 0;
                dfs(i);
                // 完全连通分量中的边数相当于从 v 个点中选 2 个点的方案数，为eCount == vCount * (vCount - 1) / 2
                // 现在统计每个点的时候会统计两次所以eCount == vCount * (vCount - 1)则认为是完全连通分量
                if (eCount == vCount * (vCount - 1)) {
                    res++;
                }
            }
        }
        return res;
    }

    public void dfs(int u) {
        visited[u] = true;
        // 统计点的数量
        vCount++;
        // 统计边的数量，加上该点出发边的数量
        eCount += adjArr[u].size();
        for (int v : adjArr[u]) {
            if (!visited[v]) {
                dfs(v);
            }
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}